﻿
#include <vector>
#include <sstream>
#include <string>
#include <iterator>
#include <algorithm>
#include <stack>
#include <cmath>
#include <iostream>

using namespace std;

bool isOperator(char c);
bool cmp(vector<int>& A, vector<int>& B);
vector<int> sub(vector<int>& A, vector<int>& B);

//将迭代器元素转化为string，注意！此时仍是低位数在前
string vector_to_string(vector<int>& A)
{
	stringstream ss;
	string str;
	copy(A.begin(), A.end(), ostream_iterator<int>(ss, ""));
	str = ss.str();
	return str;
}

//判断字符串中的括号是否匹配
bool isParentheses_match(string& a)
{
	bool verdict = true;
	stack<char> paren;

	for (int i = 0; i < a.size(); ++i)
	{
		if (a[i] == '(')
		{
			paren.push(a[i]);
			continue;
		}
		else if (a[i] == ')')
		{
			if (paren.empty())
			{
				verdict = false;
				break;
			}
			else
				paren.pop();
		}
	}

	return verdict;
}

//检验字符串是否合规
bool inspection(string& a)
{
	bool verdict = true;
	int len = a.size();

	for (int i = 0; i < len; ++i)
	{
		if (isdigit(a[i]))
		{
			if (i != len - 1 && a[i + 1] == '(')		//数字之后不能是左括号
			{
				verdict = false;
				break;
			}
			else if (i != 0 && a[i - 1] == ')')			//数字之前不能是右括号
			{
				verdict = false;
				break;
			}
			else if ((i == 0 && a[i] == '0' && isdigit(a[i + 1])) ||
				((i != len - 1 && a[i] == '0' && isdigit(a[i + 1])) && (i != 0 && !isdigit(a[i - 1]))))	//如果有多位数，则0不能在多位数前面
			{
				verdict = false;
				break;
			}
			else
				continue;
		}
		else if (isOperator(a[i]))
		{
			if (i == 0 && a[i] != '-')		//运算符除负号外不能在算式开头
			{
				verdict = false;
				break;
			}
			else if (i == len - 1)		//运算符不能在算式末尾
			{
				verdict = false;
				break;
			}
			else if (i != 0 && (isOperator(a[i - 1]) || isOperator(a[i + 1])))		//运算符不能连在一起
			{
				verdict = false;
				break;
			}
			else
				continue;
		}
		else if (a[i] == '(' || a[i] == ')')
		{
			if (a[i] == '(' && i == len - 1)		//左括号不能在末尾
			{
				verdict = false;
				break;
			}
			else if (a[i] == ')' && i == 0)			//右括号不能在开头
			{
				verdict = false;
				break;
			}
			else if (a[i] == '(' && a[i + 1] != '-' && !isdigit(a[i + 1]))		//左括号后面不能是除数字和负号外的其他东西
			{
				verdict = false;
				break;
			}
			else if (a[i] == ')' && !isdigit(a[i - 1]))			//右括号前不能是除数字外的任何东西
			{
				verdict = false;
				break;
			}
			else
				continue;
		}
		else
		{
			verdict = false;
			break;
		}
	}

	bool paren_verdict = isParentheses_match(a);
	if (!paren_verdict)
		verdict = false;

	return verdict;
}


/*前缀表达式转逆波兰表达式部分*/

//判断字符是否为运算符
bool isOperator(char c)
{
	if (c == '+' || c == '-' || c == '*' || c == '/')
		return true;
	return false;
}

//判断符号优先级
int getPriority(char c)
{
	int level = 0;

	switch (c)
	{
	case '(':
		level = 1;
		break;
	case '+':
	case '-':
		level = 2;
		break;
	case '*':
	case '/':
		level = 3;
		break;
	}

	return level;
}

//中缀表达式转逆波兰表达式算法主体
string infix_to_suffix(string& init_formula)
{
	string pro_formula;
	stack<char> op;		//一个用来存储操作符的栈

	int len, i = 0;
	char c;		//用来存储从栈中取出的操作符
	len = init_formula.size();

	while (i < len)
	{
		if (isdigit(init_formula[i]))
		{
			if (!pro_formula.empty() && isdigit(pro_formula.back()))		//格式化输出
			{
				pro_formula.push_back(' ');
			}

			do {
				pro_formula.push_back(init_formula[i++]);
			} while (isdigit(init_formula[i]));
		}
		else if (init_formula[i] == '(')
		{
			op.push(init_formula[i]);
			++i;
		}
		else if (isOperator(init_formula[i]))
		{
			if (init_formula[i] == '-' && init_formula[i + 1] != '0' && (i == 0 || init_formula[i - 1] == '('))
			{
				if (!pro_formula.empty())
					pro_formula.push_back(' ');

				pro_formula.push_back('f');		//用字母'f'表示负号
				++i;
			}
			else if (op.empty())		//如果栈为空，则直接入栈
			{
				op.push(init_formula[i++]);
			}
			else
			{
				while (!op.empty())
				{
					c = op.top();
					if (getPriority(init_formula[i]) <= getPriority(c))		//判断符号优先级
					{
						pro_formula.push_back(c);
						op.pop();
					}
					else
						break;
				}
				op.push(init_formula[i++]);
			}
		}
		else if (init_formula[i] == ')')		//如果是右括号，则一直出栈直到遇到左括号为止
		{
			while (op.top() != '(')
			{
				pro_formula.push_back(op.top());
				op.pop();
			}
			op.pop();		//将左括号出栈
			++i;		//进行下一个字符的处理
		}
	}

	while (!op.empty())		//当栈不为空则持续将符号出栈知道栈空为止
	{
		pro_formula.push_back(op.top());
		op.pop();
	}

	return pro_formula;
}


/*加法部分*/

//加法计算模块
vector<int> add(vector<int>& A, vector<int>& B)
{
	vector<int> C;
	int t = 0;	//进位计数器
	for (int i = 0; i < A.size() || i < B.size(); ++i)
	{
		if (i < A.size()) t += A[i];
		if (i < B.size()) t += B[i];

		C.push_back(t % 10);
		t /= 10;
	}

	if (t) C.push_back(t);
	return C;
}

//加法计算主体
vector<int> add_main(vector<int>& A, vector<int>& B)
{
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());

	vector<int> C;
	bool is_positive = true;

	if (A.size() > 1 && A.back() == 0 && B.back() != 0)
	{
		A.pop_back();
		is_positive = cmp(B, A);
		C = is_positive ? sub(B, A) : sub(A, B);

		if (!is_positive)
			C.push_back(0);
	}
	else if (B.size() > 1 && B.back() == 0 && A.back() != 0)
	{
		B.pop_back();
		is_positive = cmp(A, B);
		C = is_positive ? sub(A, B) : sub(B, A);

		if (!is_positive)
			C.push_back(0);
	}
	else if (A.back() == 0 && B.back() == 0 && A.size() > 1 && B.size() > 1)
	{
		A.pop_back();
		B.pop_back();
		C = add(A, B);
		C.push_back(0);
	}
	else
		C = add(A, B);

	reverse(C.begin(), C.end());
	return C;
}


/*减法部分*/

//判断两个数的大小
bool cmp(vector<int>& A, vector<int>& B)
{
	if (A.size() != B.size()) return (A.size() >= B.size());

	for (int i = A.size() - 1; i >= 0; --i)
		if (A[i] != B[i])
		{
			return A[i] >= B[i];
		}
	return true;
}

//减法实现模块
vector<int> sub(vector<int>& A, vector<int>& B)
{
	vector<int> C;

	for (int i = 0, t = 0; i < A.size(); ++i)
	{
		t = A[i] - t;
		if (i < B.size()) t -= B[i];
		C.push_back((t + 10) % 10);
		if (t < 0) t = 1;
		else t = 0;
	}

	while (C.size() > 1 && C.back() == 0) C.pop_back();		//清除前导零

	return C;
}

//减法主体函数
vector<int> sub_main(vector<int>& A, vector<int>& B)
{
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());

	vector<int> C;

	if (A.back() == 0 && B.back() != 0 && A.size() > 1)
	{
		A.pop_back();
		C = add(A, B);
		C.push_back(0);
	}
	else if (B.back() == 0 && A.back() != 0 && B.size() > 1)
	{
		B.pop_back();
		C = add(A, B);
	}
	else if (A.back() == 0 && B.back() == 0 && A.size() > 1 && B.size() > 1)
	{
		A.pop_back();
		B.pop_back();
		bool is_positive = cmp(B, A);
		C = is_positive ? sub(B, A) : sub(A, B);

		if (!is_positive)
			C.push_back(0);
	}
	else
		C = sub(A, B);

	reverse(C.begin(), C.end());
	return C;
}


/*乘法部分*/

vector<int> mul(vector<int>& A, vector<int>& B)
{
	vector<int> C(A.size() + B.size() + 7, 0);		//初始化C，C的size可以弄大点，防止越界，后面会清前导零

	for (int i = 0; i < A.size(); ++i)
		for (int j = 0; j < B.size(); ++j)
			C[i + j] = A[i] * B[j];

	int t = 0;		//设置一个进位符
	for (int i = 0; i < C.size(); ++i)		//当i < C.size() - 1时，t一定会小于10
	{
		t += C[i];
		C[i] = t % 10;
		t /= 10;
	}

	while (C.size() > 1 && C.back() == 0) C.pop_back();		//清前导零
	return C;
}

vector<int> mul_main(vector<int>& A, vector<int>& B)
{
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	vector<int> C;

	if (A.back() == 0 && B.back() != 0 && A.size() > 1)
	{
		A.pop_back();
		C = mul(A, B);
		C.push_back(0);
	}
	else if (B.back() == 0 && A.back() != 0 && B.size() > 1)
	{
		B.pop_back();
		C = mul(A, B);
		C.push_back(0);
	}
	else if (A.back() == 0 && B.back() == 0 && A.size() > 1 && B.size() > 1)
	{
		A.pop_back();
		B.pop_back();
		C = mul(A, B);
	}
	else
		C = mul(A, B);

	reverse(C.begin(), C.end());
	return C;
}


/*除法部分*/


vector<int> div(vector<int>& A, vector<int>& B)
{
	int lenA = A.size();
	int lenB = B.size();
	int differ = lenA - lenB;		//数位差

	vector<int> B1(B), C, D(A);
	int cnt = 0;

	for (int i = differ; i >= 0; )
	{
		cnt = 0;
		B1 = B;

		for (int j = i; j > 0; --j)		//让除数与被除数数位相同
			if (cmp(D, B1))
				B1.insert(B1.begin(), 0);

		if (!cmp(D, B1) && D.size() > 1 && D.back() != 0)		//若数位相同时除数大于被除数则将除数减少一位
			B1.erase(B1.begin());

		while (cmp(D, B1))
		{
			D = sub(D, B1);
			cnt += 1;
		}

		--i;
		C.push_back(cnt);
		if (D.size() == 1 && D.back() == 0)
		{
			for (int j = 0; j < i; ++j)
				C.push_back(0);
			break;
		}
		else if (!cmp(D, B))
			break;
	}

	return C;
}

vector<int> div_main(vector<int>& A, vector<int>& B)
{
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	vector<int> C;

	if (cmp(A, B))
	{
		if (A.back() == 0 && B.back() != 0 && A.size() > 1)
		{
			A.pop_back();
			C = div(A, B);
			C.insert(C.begin(), 0);
		}
		else if (A.back() != 0 && B.back() == 0 && B.size() > 1)
		{
			B.pop_back();
			C = div(A, B);
			C.insert(C.begin(), 0);
		}
		else if (A.back() == 0 && B.back() == 0 && A.size() > 1 && B.size() > 1)
		{
			A.pop_back();
			B.pop_back();
			C = div(A, B);
		}
		else
			C = div(A, B);
		
		//reverse(C.begin(), C.end());
		return C;
	}
	else
	{
		printf("除数比被除数大，无法运算，结果错误！");
		return B;
	}
}



//计算器主体函数
string suffix_operator(string& a)
{
	string b = infix_to_suffix(a);
	stack<vector<int>> A;
	vector<int> B, C;

	int i = 0;
	while (i < b.length())
	{
		if (isdigit(b[i]) || b[i] == 'f')
		{
			if (b[i] == 'f')
			{
				B.push_back(0);
				++i;
			}

			while (isdigit(b[i]))
			{
				B.push_back(b[i] - '0');
				++i;
			}
			A.push(B);
			B.clear();
		}
		else if (b[i] == ' ')
			++i;
		else if (isOperator(b[i]))
		{
			switch (b[i])
			{
			case '+':
				C = A.top();	A.pop();
				B = A.top();	A.pop();
				A.push(add_main(B, C));
				break;
			case '-':
				C = A.top();	A.pop();
				B = A.top();	A.pop();
				A.push(sub_main(B, C));
				break;
			case '*':
				C = A.top();	A.pop();
				B = A.top();	A.pop();
				A.push(mul_main(B, C));
				break;
			case '/':
				C = A.top();	A.pop();
				B = A.top();	A.pop();
				A.push(div_main(B, C));
				break;
			}
			++i;
			B.clear();	C.clear();
		}
	}

	C = A.top();
	string c = vector_to_string(C);

	if (c[0] == '0' && c.size() > 1 && c[1] != '0')			//标准化输出
		c[0] = '-';
	else if (c[0] == '0' && c.size() > 1 && c[1] == '0')
		c.pop_back();

	return c;
}


int main()
{
	printf("欢迎使用Grey_Havens开发的高精度计算器！\n\n");
	printf("该计算器目前为0.5版本，所以功能还不是很完备。\n");
	printf("您可以使用该计算器进行任意大数位的加减乘除运算\n");
	printf("您可以输入任意长度的算式，如：9+(3-1)*3+10/2 \n");
	printf("但请注意，不要让计算过程中或计算结果中出现小数，因为我们还没有完善相关的计算模块。\n");
	printf("还有，除了加减乘除和括号外，输入其他符号将被视为输入错误。\n");
	printf("好了，祝您使用愉快！\n\n");
	printf("请输入您的算式：\n");

	string a;
	cin >> a;

	if (inspection(a))
	{
		string ans = suffix_operator(a);
		cout << ans;
	}
	else
		printf("输入格式不对，请重新输入！");

	return 0;
}